package DP.LIS;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 300. 最长上升子序列
 * 给定一个无序的整数数组，找到其中最长上升子序列的长度。
 *
 * 示例:
 *
 * 输入: [10,9,2,5,3,7,101,18]
 * 输出: 4
 * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
 * 说明:
 *
 * 可能会有多种最长上升子序列的组合，你只需要输出对应的长度即可。
 * 你算法的时间复杂度应该为 O(n2) 。
 * 进阶: 你能将算法的时间复杂度降低到 O(n log n) 吗?
 */
public class lengthOfLIS {
    /**
     * 方法一：动态规划
     * @param nums 输入数组
     * @return 最长递增子序列长度
     */
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        // 1. 定义dp[i]表示以nums[i]为结尾的最长子序列长度
        int[] dp = new int[length];
        // 2. 初始化dp数组
        Arrays.fill(dp, 1);
        // 3.状态转移方程
        // dp[i] = max(dp[j] + 1 | j < i && nums[j] < nums[i], 1);
        for (int i = 1; i < length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
        }
        // 4. 求结果
        // result = max(dp)
        int result = 1;
        for (int i = 1; i < length; i++) {
            result = Math.max(dp[i], result);
        }
        return result;
    }

    /**
     * 方法二：贪心法 + 二分查找
     * @param nums
     * @return
     */
    public int lengthOfLISI(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int length = nums.length;
        int[] tails = new int[length];
        int len = 0;
        for (int i = 1; i < length; i++) {
            int index = binSearch(tails, len, nums[i]);
            tails[index] = nums[i];
            if (index == len) {
                len++;
            }
        }
        return len;
    }

    private int binSearch(int[] tails, int len, int key) {
        int l = 0;
        int h = len;
        while (l < h) {
            int mid = (l - h) / 2 + l;
            if (tails[mid] == key) {
                return mid;
            } else if (tails[mid] > key) {
                h = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    public int lengthOfLISII(int[] nums) {
        int[] tails = new int[nums.length];
        int res = 0;
        for(int num : nums) {
            int i = 0, j = res;
            while(i < j) {
                int m = (i + j) / 2;
                if(tails[m] < num) i = m + 1;
                else j = m;
            }
            tails[i] = num;
            if(res == j) res++;
        }
        return res;
    }
}
